1. Field of the Invention
The present invention relates to Booth recoded multipliers; and more particularly, power efficient Booth recoded multipliers.
2. Description of Related Art
A standard approach that might be taken by a novice to multiplication is to “shift and add”, or normal “long multiplication”. That is, for each column in the multiplier, shift the multiplicand the appropriate number of columns and multiply it by the value of the digit in that column of the multiplier, to obtain a partial product. The partial products are then added to obtain the final result:
                                                                                                                            0              0              1              0              1              1                                                                                                                                  0              1              0              0              1              1                                                                                                                                  0              0              1              0              1              1                                                                                                      0              0              1              0              1              1                                                                                                      0              0              0              0              0              0                                                                                                      0              0              0              0              0              0                                                                                                      0              0              1              0              1              1                                                                                                                                  0              0              1              1              0              1              0              0              0              1      With this system, the number of partial products is exactly the number of columns in the multiplier.
It is possible to reduce the number of partial products by half using the technique of radix 4 Booth recoding. The basic idea is that, instead of shifting and adding for every column of the multiplier term and multiplying by 1 or 0, we only take every second column, and multiply by ±1, ±2, or 0, to obtain the same results. So, to multiply by 7, we can multiply the partial product aligned against the least significant bit by −1, and multiply the partial product aligned with the third column by 2:Partial Product 0=Multiplicand*−1, shifted left 0 bits (×−1)Partial Product 1=Multiplicand*2, shifted left 2 bits (×8)
This is the same result as the equivalent shift and add method:Partial Product 0=Multiplicand*1, shifted left 0 bits (×1)Partial Product 1=Multiplicand*1, shifted left 1 bits (×2)Partial Product 2=Multiplicand*1, shifted left 2 bits (×4)Partial Product 3=Multiplicand*0, shifted left 3 bits (×0)
The advantage of this method is the halving of the number of partial products. This is important in circuit design as it relates to the propagation delay in the running of the circuit, and the complexity and power consumption of its implementation.
It is also important to note that there is comparatively little complexity penalty in multiplying by 0, 1 or 2. All that is needed is a multiplexer or equivalent, which has a delay time that is independent of the size of the inputs. Negating 2's complement numbers has the added complication of needing to add a “1” to the LSB, but this can be overcome by adding a single correction term with the necessary “1”s in the correct positions.
To Booth recode the multiplier term, the bits of the multiplier operand are considered in blocks of three, such that each block overlaps the previous block by one bit. Grouping starts from the LSB, and the first block only uses two bits of the multiplier (since there is no previous block to overlap):

The overlap is necessary so that what happened in the last block is known, as the MSB of the block acts like a sign bit. The following table is then consulted to decide what the encoding will be:
BlockPartial Product0000001 1 * Multiplicand010 1 * Multiplicand011 2 * Multiplicand100−2 * Multiplicand101−1 * Multiplicand110−1 * Multiplicand1110
Since the LSB of each block is used to know what the sign bit was in the previous block, and there are never any negative products before the least significant block, the LSB of the first block is always assumed to be 0. Hence, we would recode our example of 7 (binary 0111) as such:
0111block 0:110Encoding: *(−1)block 1:011Encoding: *(2)
In the case where there are not enough bits to obtain a MSB of the last block, we sign extend the multiplier by one bit:
00111block 0:110Encoding: *(−1)block 1:011Encoding: *(2)block 2:000Encoding: *(0)The previous example then becomes:
001011, multiplicand010011, multiplier11−1, booth encoding ofmultiplier1111110100, negative term signextended0000101100101100001, error correction fornegation0011010001, discarding the carriedhigh bit
Booth recoders, their structure and use in multipliers, are described by N. Weste and K. Eshraghian on pages 547–554 of Principles of CMOS VLSI Design, 2nd Ed, Addison Wesley 1992.
Depending on the size of the multiplier and multiplicand (the two operands in the multiplication), Booth recoders reduce the critical path of multipliers when implemented in hardware, software, etc. Namely, the processing time through the multiplier is reduced as compared to when Booth recoding is not employed. This is important because multipliers tend to have the longest processing time of all the functional units.
Besides processing time, power consumption is another important issue of concern when designing multipliers. Because the multiplier operates on the operands along with other functional units, regardless of whether the product produced by the multiplier is needed, needless power consumption takes place. There are a number of traditional methods that have been used to render the output of the multiplier constant, and thus reduce power consumption by the multiplier. One approach involves ANDing one or both of the operands (multiplier and multiplicand) with an enable signal and ANDing the negative Booth recoded signal, which indicates whether to take the negative of the partial product being generated, with the enable signal. When the enable signal is set to one, the multiplier performs in the same manner as if the enable circuitry were absent. Accordingly, partial products are determined based on the multiplicand operand and the Booth recoded outputs, which are generated based on the multiplier operand, and a negative of the partial product is chosen based on the negative Booth recoded output. However, when the enable signal is sent to zero, the multiplicand operand is zeroed out by the ANDing with the enable signal, and a negative of the resulting zero partial product is not generated because the negative Booth recoded output is zeroed out by being ANDed with the enable signal. A still further method requires creating an inverse of the negative Booth recoded signal, ANDing the negative and inverse negative Booth recoded signals with the enable signal, and using the resultant output to control whether a partial product or its negative are output such that the output of the partial product circuit remains constant.